import copy

arr = [ 30, 27, 18, 48, 60, 7, 51, 19, 48, 53]



def change(p_index, arr):
    length = len(arr)
    r_index = 2 * p_index + 1
    l_index = 2 * p_index
    max_num = arr[p_index]
    max_index = None
    r_chird = arr[r_index] if r_index <= length - 1 else None
    l_chird = arr[l_index] if l_index <= length - 1 else None
    if r_chird is not None and r_chird > max_num:
        max_num = r_chird
        max_index = r_index

    if l_chird is not None and l_chird > max_num:
        max_num = l_chird
        max_index = l_index

    if max_index is not None:
        arr[max_index] = arr[p_index]
        arr[p_index] = max_num
        change(max_index, arr)

def sift(arr):
    print(f"初始{arr}")
    length = len(arr)
    le = int(length/2) # 节点长度
    for i in range(le, 0, -1):
        change(i, arr)
        print(f'{i}{arr}')


def heap_sort(arr):
    index = len(arr) - 1
    copy_arr = copy.deepcopy(arr)
    copy_arr.insert(0,None)
    while len(copy_arr) > 1:
        sift(copy_arr)
        a = copy_arr[1]
        copy_arr[1] = copy_arr[len(copy_arr)-1]
        copy_arr[len(copy_arr)-1] = a
        arr[index] = copy_arr.pop()
        index -= 1



heap_sort(arr)
print(arr)



